package com.javaDemo.ti;

import java.util.HashSet;
import java.util.Set;

/**
 * 无重复字符的最长子串
 * 
 * @author ayuea
 * @description 给定一个字符串，找出其中不含有重复字符的最长子串的长度
 * 
 *              解题思路：
 *              1. 使用滑动窗口法，维护一个不含重复字符的窗口
 *              2. 使用HashSet存储窗口中的字符
 *              3. 右指针不断向右扩展，直到遇到重复字符
 *              4. 左指针向右移动，移除字符直到不再重复
 *              5. 在整个过程中记录最大窗口长度
 * 
 *              时间复杂度：O(n)，其中n是字符串长度
 *              空间复杂度：O(min(m,n))，其中m是字符集大小
 * 
 *              示例：
 *              输入: "abcabcbb"
 *              输出: 3
 *              解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3
 */
public class LongestSubstringWithoutRepeating {

    public static void main(String[] args) {
        // 测试用例
        String[] testCases = {
                "abcabcbb", // 期望输出：3 ("abc")
                "bbbbb", // 期望输出：1 ("b")
                "pwwkew", // 期望输出：3 ("wke")
                "" // 期望输出：0
        };

        // 执行测试
        for (String str : testCases) {
            int result = findLongestSubstring(str);
            System.out.printf("字符串 \"%s\" 的无重复字符最长子串长度为：%d%n",
                    str, result);
        }
    }

    /**
     * 查找无重复字符的最长子串长度
     * 
     * @param str 输入字符串
     * @return 最长无重复子串的长度
     */
    public static int findLongestSubstring(String str) {
        // 特殊情况处理
        if (str == null || str.isEmpty()) {
            return 0;
        }

        // 使用HashSet存储当前窗口中的字符
        Set<Character> windowChars = new HashSet<>();
        int maxLength = 0; // 最长子串长度
        int leftPtr = 0; // 窗口左边界
        int rightPtr = 0; // 窗口右边界
        int strLength = str.length();

        // 使用滑动窗口遍历字符串
        while (rightPtr < strLength) {
            char currentChar = str.charAt(rightPtr);

            // 如果当前字符已在窗口中，移动左指针直到删除重复字符
            while (windowChars.contains(currentChar)) {
                windowChars.remove(str.charAt(leftPtr));
                leftPtr++;
            }

            // 将当前字符添加到窗口中
            windowChars.add(currentChar);

            // 更新最大长度
            maxLength = Math.max(maxLength, rightPtr - leftPtr + 1);

            // 移动右指针
            rightPtr++;
        }

        return maxLength;
    }
}